/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode guard(-1);
        while (head!=NULL) {
            ListNode *data=head;
            head=head->next;
            ListNode *x=&guard;
            while (x->next!=NULL && x->next->val<data->val) x=x->next;
            data->next=x->next;
            x->next=data;
        }
        return guard.next;
    }
};

